import java.util.*;

/**
 * 1382. 将二叉搜索树变平衡
 * https://leetcode-cn.com/problems/balance-a-binary-search-tree/
 */
public class Solutions_1382 {
    public static void main(String[] args) {
        String rootStr = "[1 # 2 # 3 # 4]";
        TreeNode root = MyTreeNodeUtils.deserialize(rootStr);
        TreeNode result = balanceBST(root);
        System.out.println(MyTreeNodeUtils.serialize(result));
    }

    private static List<TreeNode> list = null;
    public static TreeNode balanceBST(TreeNode root) {
        // 通过中序遍历，将 root 中元素都添加到 list 中（list 中直接记录节点对象而不是节点值，可以省掉创建节点的过程）
        list = new ArrayList<>();
        addRootToList(root);

        // 根据 list 中的元素构建成平衡二叉树
        TreeNode res = buildTree(0, list.size() - 1);
        return res;
    }

    /**
     * 分治思想，根据 list 中的元素构建成平衡二叉树
     */
    public static TreeNode buildTree(int left, int right) {
        if (left > right) {
            return null;
        }
        // 找到中间位置
        int mid = left + (right - left) / 2;
        TreeNode root = list.get(mid);
        // 构建左子树
        root.left = buildTree(left, mid - 1);
        // 构建右子树
        root.right = buildTree(mid + 1, right);
        return root;
    }

    /**
     * 迭代完成
     */
    public static void addRootToList(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode temp = stack.pop();
            list.add(temp);
            cur = temp.right;
        }
    }
}
